package leetcode;

import java.beans.EventHandler;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class LC207CourseSchedule {



    //拓扑排序
    public boolean canFinish2222222222(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        HashMap<Integer, List> adjacency = new HashMap<>();
        //统计每个点的入度 记录每个点的后继节点
        for (int i = 0; i < prerequisites.length; i++) {
            int u = prerequisites[i][0];
            int v = prerequisites[i][1]; // v -> u
            indegree[u] ++;
            List nextCorse = adjacency.getOrDefault(v, new ArrayList<Integer>());
            nextCorse.add(u);
            adjacency.put(v,nextCorse);
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0)
                queue.offer(i);
        }
        int cnt = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            cnt ++;
            List<Integer> nextCourses = adjacency.get(u);
            if (nextCourses == null) continue;
            for (int i = 0; i < nextCourses.size(); i++) {
                indegree[nextCourses.get(i)] --;
                if (indegree[nextCourses.get(i)] == 0)
                    queue.offer(nextCourses.get(i));
            }
        }
        return cnt == numCourses;
    }


    //入度0队列判断是否有环
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        int[] inDegree = new int[numCourses];
        HashMap<Integer, ArrayList<Integer>> nextCourses = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][0];
            int b = prerequisites[i][1];
            inDegree[a] ++;

            ArrayList<Integer> nextCourse  = nextCourses.getOrDefault(b,new ArrayList<>());
            nextCourse.add(a);
            nextCourses.put(b,nextCourse);
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.removeFirst();
            count ++;
            ArrayList<Integer> next = nextCourses.getOrDefault(course,new ArrayList<>());
            for (int i = 0; i < next.size(); i++) {
                inDegree[next.get(i)] --;
                if (inDegree[next.get(i)] == 0) {
                    queue.add(next.get(i));
                }
            }
        }
        if (count != numCourses) return false;
        return true;
    }


}
